package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 回文链表
 * @date 24/5/6 23:12
 */
public class Leetcode234 {

	public static void main(String[] args) {
		// System.out.println(isPalindrome(ListNode.of(1, 2, 3, 1)));
		// System.out.println(isPalindrome(ListNode.of(1, 2, 3, 2, 1)));
		System.out.println(isPalindromeOptimize(ListNode.of(1, 2, 3, 1)));
		System.out.println(isPalindromeOptimize(ListNode.of(1, 2, 3, 2, 1)));
	}

	/**
	 * 逻辑思路：
	 * 1、找中间点
	 * 2、中间点之后的半个链表反转
	 * 3、反转后链表与原链表逐一比较
	 *
	 * @param head
	 * @return
	 */
	private static boolean isPalindrome(ListNode head) {
		ListNode middle = middle(head);
		System.out.println(middle);
		ListNode newHead = reverse(middle);
		System.out.println(newHead);

		while (newHead != null) {
			if (newHead.val != head.val) {
				return false;
			}
			newHead = newHead.next;
			head = head.next;
		}
		return true;
	}

	/**
	 * 优化思路：
	 * 1、找中间点，并且反转前半个链表
	 * 2、反转后的前半个链表 和 中间点开始的后半个链表逐一比较
	 *
	 * @param head
	 * @return
	 */
	private static boolean isPalindromeOptimize(ListNode head) {

		// 1、找中间点，并反转
		ListNode p1 = head; // 慢指针
		ListNode p2 = head; // 快指针
		ListNode n1 = null; // 新头
		ListNode o1 = head; // 旧头

		// p2 == null 偶数节点，p2.next == null 奇数节点
		while (p2 != null && p2.next != null) {
			p1 = p1.next;
			p2 = p2.next.next;

			// 2、反转链表
			// ListNode o2 = o1.next;
			// o1.next = n1;
			// n1 = o1;
			// o1 = o2;

			// 2、反转链表【o2 == o1.next == p1.next，优化一下就是直接使用p1】
			o1.next = n1;
			n1 = o1;
			o1 = p1;
		}

		// 奇数节点
		if (p2 != null) {
			p1 = p1.next;
		}

		System.out.println(n1);
		System.out.println(p1);

		// 3、逐一比较
		while (p1 != null) {
			if (p1.val != n1.val) {
				return false;
			}
			p1 = p1.next;
			n1 = n1.next;
		}

		return true;
	}


	/**
	 * o1 o2
	 * 1  2  3  4 null -> 2 3 4 null -> 3 4 null -> 4 null
	 * n1
	 * null -> 1 null -> 2 1 null -> 3 2 1 null -> 4 3 2 1 null
	 *
	 * @param o1
	 * @return
	 */
	private static ListNode reverse(ListNode o1) {
		ListNode n1 = null;
		while (o1 != null) {
			ListNode o2 = o1.next;
			o1.next = n1;
			n1 = o1;
			o1 = o2;
		}
		return n1;
	}

	// 找中间节点
	private static ListNode middle(ListNode head) {
		ListNode p1 = head; // 慢指针
		ListNode p2 = head; // 快指针
		while (p2 != null && p2.next != null) {
			p1 = p1.next;
			p2 = p2.next.next;
		}
		return p1;
	}

}
